package showtime.framework.algorithm.astar
{
	import showtime.framework.algorithm.collections.BinaryHeap;
	
	import flash.utils.getTimer;
	
	
	
	public class Astar
	{
		/**
		 * Open node table 
		 */		
		private var _open:BinaryHeap = null;
		/**
		 * Closed node table 
		 */		
		private var _closed:Array = null;
		private var _mapModel:MapModel = null;
		private var _endNode:Node = null;
		private var _startNode:Node = null;
		private var _path:Array = null;
		/**
		 * Heuristic function 
		 */		
		private var _heuristic:Function = diagonal;
		private var _straightCost:Number = 1.0;
		private var _diagCost:Number = Math.SQRT2;
		
		public function Astar(mapModel:MapModel)
		{
			_mapModel = mapModel;
		}
		
		public function search(startX:int, startY:int, endX:int, endY:int):SearchResults
		{			
			var searchResult:SearchResults = new SearchResults();
			
			_open = new BinaryHeap("f");
			_closed = [];
			
			_startNode = _mapModel.getNode(startX, startY);
			_endNode = _mapModel.getNode(endX, endY);
			
			_startNode.g = 0;
			_startNode.h = _heuristic(_startNode);
			_startNode.f = _startNode.g + _startNode.h;
			
			
			var startTime:int=getTimer();
			var node:Node = _startNode;
			var sortTime:int = 0;
			var tryCount:int = 0;
			
			while(node != _endNode)
			{
				tryCount++;
				var startX:int = 0 > node.x - 1 ? 0 : node.x - 1;
				var endX:int = _mapModel.cols - 1 < node.x + 1 ? _mapModel.cols - 1 : node.x + 1;
				var startY:int = 0 > node.y - 1 ? 0 : node.y - 1;
				var endY:int = _mapModel.rows - 1 < node.y + 1 ? _mapModel.rows - 1 : node.y + 1;				
				
				for(var i:int = startX; i <= endX; i++)
				{
					for(var j:int = startY; j <= endY; j++)
					{
						var currentNode:Node = _mapModel.getNode(i, j);
						if(currentNode == node)
						{
							continue;
						}
						
						if( !currentNode.walkable || !isDiagonalWalkable(node, currentNode) )
						{
							currentNode.costMultiplier = int.MAX_VALUE;
						}
						else
						{
							currentNode.costMultiplier = 1;
						}
						
						var cost:Number = _straightCost;
						
						if (!((node.x == currentNode.x) || (node.y == currentNode.y)))
						{
							cost = _diagCost;
						}
						
						var g:Number = node.g + cost * currentNode.costMultiplier;
						var h:Number = _heuristic(currentNode);
						var f:Number = g + h;
						var isInOpen:Boolean = _open.indexOf(currentNode) != -1;
						if( isInOpen || _closed.indexOf(currentNode) != -1)
						{
							if(currentNode.f > f)
							{
								currentNode.f = f;
								currentNode.g = g;
								currentNode.h = h;
								currentNode.parent = node;
								if( isInOpen )
									_open.update( currentNode );
							}
						}
						else
						{
							currentNode.f = f;
							currentNode.g = g;
							currentNode.h = h;
							currentNode.parent = node;

							_open.push(currentNode);
						}
					}
				}
				_closed.push(node);
				
				if (_open.length == 0)
				{					
					return searchResult;
				}
				
				var sortStartTime:int = getTimer();

				node = _open.shift() as Node;
				sortTime += (getTimer() - sortStartTime);
			}
//			trace( "time cost: " + (getTimer() - startTime) + "ms");
//			trace( "sort cost: " + sortTime);
//			trace( "try time: " + tryCount);
			
			buildPath();
			
			searchResult.path = _path;
			searchResult.result = true;
			
			return searchResult;
			
		}
		
		/**
		 * Build path; 
		 * 
		 */		
		private function buildPath():void
		{
			_path = [];
			
			var node:Node = _endNode;
			_path.push(node);
	
			while(node.parent != _startNode)
			{
				node = node.parent;
				_path.unshift(node);
			}
		
			var len:int = _path.length;
			
			for(var i:int=0; i < len; i++ )
			{
				if( _path[i].walkable == false )
				{
					_path.splice(i, len - i);
					break;
				}
				else if(len == 1 && !isDiagonalWalkable(_startNode, _endNode))
				{
					_path.shift();
				}
				else if(i < len - 1 && !isDiagonalWalkable(_path[i], _path[i + 1]))
				{
					_path.splice(i + 1, len - i - 1);
					break;
				}
			}
		}
		
		public function get path():Array
		{
			return _path;
		}
		
		private function isDiagonalWalkable( node1:Node, node2:Node ):Boolean
		{
			var nearByNode1:Node = _mapModel.getNode( node1.x, node2.y );
			var nearByNode2:Node = _mapModel.getNode( node2.x, node1.y );
			
			if( nearByNode1.walkable && nearByNode2.walkable )
			{
				return true;
			}
			return false;
		}
		
		private function manhattan(node:Node):Number
		{
			return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
		}
		
		private function euclidian(node:Node):Number
		{
			var dx:Number = node.x - _endNode.x;
			var dy:Number = node.y - _endNode.y;
			return Math.sqrt(dx * dx + dy * dy) * _straightCost;
		}
		
		private function diagonal(node:Node):Number
		{
			var dx:Number = node.x - _endNode.x < 0 ? _endNode.x - node.x : node.x - _endNode.x;
			var dy:Number = node.y - _endNode.y < 0 ? _endNode.y - node.y : node.y - _endNode.y;
			var diag:Number = dx < dy ? dx : dy;
			var straight:Number = dx + dy;
			return _diagCost * diag + _straightCost * (straight - 2 * diag);
		}

	}
}
